package hashBuck;

// 哈希桶的实现2：plus版（泛型）

import java.util.Objects;

public class HashBuck2<K,V> {
    //同样西哟啊一个结点类，但是key、val类型是泛型
    static class Node<K,V> {
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }

        // 重写equals和hashCode方法
        // （其实是需要在泛型K中重写equals和toString方法）！！！

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?, ?> node = (Node<?, ?>) o;
            return Objects.equals(key, node.key) && Objects.equals(val, node.val) && Objects.equals(next, node.next);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key, val, next);
        }
    }

    // 给出一个数组
    // 注意：java中不能new泛型类型的数组：如 public Node<K,V>[] arr = new Node<K,V>[10];是error
    public Node<K,V>[] arr = (Node<K, V>[]) new Node[10];
    // 也可以修改为： public Node<K,V>[] arr = (Node<K, V>[]) new Object[10];

    public int usedSize;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 写一个put方法：
    public void put(K key, V val) {
        // 变成结点
        Node<K,V> node = new Node<>(key,val);
        // 找数组位置:泛型--注意计算的方式！！
        int index = key.hashCode() % arr.length;
        // 开始遍历该数组位置的链表结点
        Node<K,V> cur = arr[index];
        while (cur != null) {
            // 注意：引用类型比较大小不是直接使用==，而是使用equals--要重写equals方法
            // 此时相当于：hashCode找在数组中的位置，而equals则是遍历该位置下的链表找相同的节点
            if(cur.key.equals(key)) {
                // 替换val
                cur.val = val;
                return;
            }
            // 来到这儿：走向链表的下一个结点位置
            cur = cur.next;
        }
        // 找到了位置开始进行头插
        node.next = arr[index];
        arr[index] = node;
        this.usedSize++;

        // 检查负载因子
        if(loadFac() >= DEFAULT_LOAD_FACTOR) {
            grow();
        }
    }

    /** 返回当前的负载因子：
     *
     * @return 返回负载因子，用于检查负载因子以及扩容
     */
    private float loadFac() {
        return usedSize * 1.0f / arr.length; // * 1.0f的目的是返回float类型
    }

    /** 扩容：
     *
     */
    private void grow() {
        Node<K,V>[] newArr = new Node[2*arr.length];
        // 遍历原数组
        for (int i = 0; i < arr.length; i++) {
            HashBuck2.Node<K,V> cur = arr[i]; // 记录当前的数组的元素对应链表的头结点
            // 遍历该链表的每一个结点 并重新进行哈希（新长度）
            while(cur != null) {
                Node<K,V> curNext = cur.next; // 记录原来cur的下一个结点（很好的保证了原来数据链表的有效）
                int index = cur.key.hashCode() % newArr.length;
                // 然后以头插法的形式插入到新的数组
                cur.next = newArr[index]; // 表示新老数组结点的对应关系
                newArr[index] = cur; // 对新数组开始赋值结点/链表
                // cur = cur.next; // 这样就会丢失原数组的后面的链表结点
                cur = curNext; // 进行循环变化的条件
            }
        }
        // 赋值到原数组
        this.arr = newArr;
    }


    /**
     * 通过key获取val
     */
    public V get(K key) {
        // 找数组下标 并进行链表的遍历比较key值返回val
        int hash = key.hashCode();
        int index = hash % arr.length;

        Node<K,V> cur = arr[index];
        while(cur != null) {
            if(cur.key.equals(key)) {
                return cur.val;
            }
            cur = cur.next;
        }
        // 来到这儿 找不到
        return null;
    }
}
